import random

# 顺序交叉-保留父代1的子序列，用父代2的剩余城市填充
def order_crossover(parent1, parent2):
    size = len(parent1)
    start, end = sorted(random.sample(range(size), 2))
    child = [-1] * size 
    child[start:end+1] = parent1[start:end+1]

    pointer = 0
    for i in range(size):
        if child[i] == -1: 
            while parent2[pointer] in child:
                pointer = (pointer + 1) % size
            child[i] = parent2[pointer]
            pointer = (pointer + 1) % size
    
    return child